博弈论4 [杂题]

①[POJ 2975] Nim
原题链接：http://poj.org/problem?id=2975
题目大意：给定一个$n$个石子，每次可以取$k_i$个石子的$Nim$游戏。问先手必胜的操作方案有几种。
数据范围：
多组测试数据
$1 \leq n \leq 1000$
$1 \leq k_i \leq 10^9$
样例输入：

3
7 11 13
2
1000000000 1000000000
0

样例输出：

3
0

首先，如果异或和为$0$显然答案为0。
其次考虑有多少种方案使得初始状态能走到一个必败态：
即对于每一个$k_i$来说，是否能移动若干个他里面的石子导致异或值到$0$。记异或和为$S$，显然$S$非$0$，对于当前的某一个$k_i$来说其他的异或和为$S \oplus k_i$，若加上了与$k_i$的异或和变成了$0$，则需要满足除去他之外的异或和是大于他的，即$S \oplus k_i < k_i$，当满足了这个条件之后，存在从$k_i$里移动若干个石块使得他的数量变成$S \oplus k_i$，使异或和变成0。
因此答案就是满足$S \oplus k_i < k_i$的数的个数。

②[POJ 3537]Crosses andCrosses
题目大意：有一个$1*n$的长条格子纸，每次可以往上画一个$X$，最先连出三个的胜利。问是否先手必胜。
注意：原题面虽然没说，但是实际上本题是有多组测试数据的。
数据范围：
多组测试数据
$1 \leq n \leq 2000$
样例输入：

3
6

样例输出：

1
2

可以发现，如果往某一个位置上填了，那么可以等价于前后两个连续的格子都不能放了，于是就可以把这个问题转换成多个有向图游戏的和。记忆化搜索分隔两边分别求救可以了。
不过这个题$set$的效率会非常垃圾。用数组+$memset$。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
typedef long long ll;
const int N = 2005;
int f[N],n;
int sg(int n)
{
	if(n <= 0)	return 0;
	if(f[n] != -1)	return f[n];
	bool st[n + 2];
	memset(st,0,sizeof st);
	for(int i = 1;i <= n;++i)
		st[sg(i - 3) ^ sg(n - i - 2)] = 1;
	int res = 0;
	while(st[res])	++res;
	return f[n] = res;	
}
int main(){
    memset(f,-1,sizeof f);
    while(~scanf("%d",&n))
    	puts(sg(n)?"1":"2");
    return 0;
}

③[Codeforces 138D]World of Darkraft
题目大意：有一$n*m$的格子纸，上面写有$L,R,X$三种字符。每次可以选一个字符删去它的同时，如果是$L$则删去左下右上的所有格子，如果是$R$则删去右下左上的所有格子，如果是$X$则同时视作$L$和$R$。问是否先手必胜。
数据范围：$1 \leq n,m \leq 20$
样例输入：

2 2
RL
LR

2 2
RR
RR

样例输出：

LOSE

WIN

对角线上的操作难以分割状态，可以把整个棋局旋转$45°$，实际的坐标变换就是：$(x,y) -> (x + y, x - y +m)$，映射结束之后，新的图上$L$就是横向切一刀，$R$就是纵向切一刀。同时整个棋局是可以二染色的，对于二染色之后的图来说，上面的不同颜色的点之间的状态是可以忽视的。因此可以分别求解。
在新图上，对应的坐标范围在$(0,0)$到$(n+m,n+m)$之间。标记当前是找黑色的状态还是白色的状态，分别求出两个$SG$值，两者由于独立，异或和大于$0$就先手必胜。
关于这个题为什么入口的坐标可以取整个范围，我个人的理解是这个坐标只是一个范围，标记了整个图上的状态范围。可能这个范围偏大，但是不合法的坐标也不会计入。把范围放大一点可以避免有坐标没算进去。但是这个做法是有一点神棍元素，暂时没想到更好的精确的方法，如果想到了再更新内容。
代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 50;
char g[N][N];
int f[N][N][N][N][2];
int n,m;
int sg(int x1,int y1,int x2,int y2,int flag)
{
	if(x1 > x2 || y1 > y2)	return 0;
	if(f[x1][y1][x2][y2][flag] != -1)	return f[x1][y1][x2][y2][flag];
	bool st[400];
	memset(st,0,sizeof st);
	
	for(int i = 1;i <= n;++i)
	{
		for(int j = 1;j <= m;++j)
		{
			int x = i + j,y = i - j + m;
			if((i + j & 1) == flag || x1 > x || x > x2 || y1 > y || y > y2)	continue;
			if(g[i][j] == 'L')	st[sg(x + 1,y1,x2,y2,flag) ^ sg(x1,y1,x - 1,y2,flag)] = 1;	
			if(g[i][j] == 'R')	st[sg(x1,y + 1,x2,y2,flag) ^ sg(x1,y1,x2,y - 1,flag)] = 1;
			if(g[i][j] == 'X')	st[sg(x + 1,y + 1,x2,y2,flag) ^ sg(x1,y1,x - 1,y - 1,flag) ^ sg(x + 1,y1,x2,y - 1,flag) ^ sg(x1,y + 1,x - 1,y2,flag)] = 1;
		}
	}
	
	int res = 0;
	while(st[res])	++res;
	return f[x1][y1][x2][y2][flag] = res;	
}
int main()
{
	scanf("%d%d",&n,&m);
	memset(f,-1,sizeof f);
	for(int i = 1;i <= n;++i)	scanf("%s",g[i] + 1);
	if(sg(0,0,n + m,n + m,1) ^ sg(0,0,n + m,n + m,0))	puts("WIN");
	else puts("LOSE");
    return 0;
}